import java.util.Arrays;
import java.util.Random;
import java.util.concurrent.ExecutionException;
import java.util.concurrent.ForkJoinPool;
import java.util.concurrent.Future;
import java.util.concurrent.RecursiveAction;

public class ForkAndJoinSort extends RecursiveAction {

    public static void main(String[] args) {
        int count = 10000000;
        int[] arr1 = new int[count];
        int[] arr2 = new int[count];
        Random random = new Random();
        for (int i = 0; i < arr1.length; i++) {
            arr1[i] = random.nextInt(count) + 1;
            arr2[i] = arr1[i];
        }
        long startTime = System.currentTimeMillis();
        ForkJoinPool forkJoinPool = new ForkJoinPool();
        ForkAndJoinSort task = new ForkAndJoinSort(arr1, 0, arr1.length - 1);
        Future<Void> result = forkJoinPool.submit(task);
        try {
            result.get();
            System.out.println("耗时：" + (System.currentTimeMillis() - startTime) + "ms");
        } catch (InterruptedException | ExecutionException e) {
            e.printStackTrace();
        }
        startTime = System.currentTimeMillis();
        Arrays.sort(arr2);
        System.out.println("耗时：" + (System.currentTimeMillis() - startTime) + "ms");
    }

    private int[] array;
    private int left;
    private int right;

    public ForkAndJoinSort(int[] array, int left, int right) {
        this.array = array;
        this.left = left;
        this.right = right;
    }

    @Override
    protected void compute() {
        int pivot = partition(array, left, right);
        ForkAndJoinSort task1 = null;
        ForkAndJoinSort task2 = null;
        if (pivot - left > 1) {
            task1 = new ForkAndJoinSort(array, left, pivot - 1);
            task1.fork();
        }
        if (right - pivot > 1) {
            task2 = new ForkAndJoinSort(array, pivot + 1, right);
            task2.fork();
        }
        if (task1 != null && !task1.isDone()) {
            task1.join();
        }
        if (task2 != null && !task2.isDone()) {
            task2.join();
        }
    }

    public int partition(int[] a, int left, int right) {
        int midle = a[left];
        while (left < right) {
            while (left < right && a[right] >= midle) {
                right--;
            }
            swap(a, left, right);
            while (left < right && a[left] <= midle) {
                left++;
            }
            swap(a, left, right);
        }
        return left;
    }
    public void swap(int[] a, int i, int j) {
        a[i] = a[i] ^ a[j];
        a[j] = a[i] ^ a[j];
        a[i] = a[i] ^ a[j];
    }
}
